package 算法练习;

import java.util.Scanner;

/**
 * 
 * @author ：soulstones
 * @version ：2019年9月16日 上午9:44:14 @Description：
 * 
 *          请实现有重复数字的有序数组的二分查找。 输出在数组中第一个大于等于查找值的位置，如果数组中不存在这样的数，则输出数组长度加一。
 */
public class 二分查找 {
	public static void main(String[] args) {
		Scanner input = new Scanner(System.in); // 输入
		while (input.hasNextInt()) {
			int length = input.nextInt(); // 输入数组长度
			int value = input.nextInt(); // 输入查询值
			int array[] = new int[length];
			for (int i = 0; i < length; i++) {
				array[i] = input.nextInt(); // 输入数组元素值
			}
			int low = 0; // 设置边界左端位置
			int high = length - 1; // 设置边界右端位置
			while (low <= high) {
				if (array[(low + high) / 2] < value) { // 若此段中间位置值小于查询值
					low = (low + high) / 2 + 1; // 说明查询值位于此段右半段
				}
				if (array[(low + high) / 2] >= value) { // 若此段中间位置值大于等于查询值
					high = (low + high) / 2 - 1; // 说明查询值位于此段右半段
				}
			}
			if (low == length || high == -1) {
				if (high == length - 1 && array[high] >= value) {
					System.out.println(high + 1);
				} else if (low == 0 && array[low] >= value) {
					System.out.println(low + 1);
				} else { // 说明查询值并不位于此数组中
					System.out.println(length + 1);
				}
			} else {
				if (array[low] >= value && array[high] >= value) {
					System.out.println(high + 1);
				}
				if (array[low] >= value && array[high] < value) {
					System.out.println(low + 1);
				}
			}
		}
	}
}
